Authentication can enable a sender to provide trustworthy proof of identity and origination to communication partners, for example, with a verifiable signature. This is an important security attribute for current applications that rely on electronic communications over insecure or public networks. The sender's identity should be protected for some applications while maintaining verifiable proof of identity and origination. Group signatures (GSs) can provide such privacy-preserving authentication (PPA). A wide variety of applications use PPA, including safety applications for vehicular networks, identity escrow schemes, anonymous credential systems, remote attestation of computing platforms, and device-to-device communications in the Internet-of-Things (IoT) paradigm. However, modern GS schemes have limited practical value for use in large networks. For example, current GS schemes use deterministic revocation, going through a revocation list and checking whether any of the revoked tokens in the revocation list correspond to a received signature. These schemes have high computational complexity of their revocation check procedures when there are a large number of revoked keys.